In triangle $ABC,$ $AB = 3,$ $AC = 6,$ and $\cos \angle A = \frac{1}{8}.$  Find the length of angle bisector $\overline{AD}.$
Explanation: By the Law of Cosines on triangle $ABC,$
\[BC = \sqrt{3^2 + 6^2 - 2 \cdot 3 \cdot 6 \cdot \frac{1}{8}} = \frac{9}{\sqrt{2}}.\][asy]
unitsize (1 cm);

pair A, B, C, D;

B = (0,0);
C = (9/sqrt(2),0);
A = intersectionpoint(arc(B,3,0,180),arc(C,6,0,180));
D = interp(B,C,3/9);

draw(A--B--C--cycle);
draw(A--D);

label("$A$", A, N);
label("$B$", B, SW);
label("$C$", C, SE);
label("$D$", D, S);
[/asy]

By the Angle Bisector Theorem, $\frac{BD}{AB} = \frac{CD}{AC},$ so $\frac{BD}{3} = \frac{CD}{6}.$  Also, $BD + CD = \frac{9}{\sqrt{2}},$ so $BD = \frac{3}{\sqrt{2}}$ and $CD = \frac{6}{\sqrt{2}}.$

By the Law of Cosines on triangle $ABC,$
\[\cos B = \frac{9 + \frac{81}{2} - 36}{2 \cdot 3\cdot \frac{9}{\sqrt{2}}} = \frac{\sqrt{2}}{4}.\]Then by the Law of Cosines on triangle $ABD,$
\[AD = \sqrt{9 + \frac{9}{2} - 2 \cdot 3 \cdot \frac{3}{\sqrt{2}} \cdot \frac{\sqrt{2}}{4}} = \boxed{3}.\]